package com.bwt.linkedList;

public class Josephu {
	public static void main(String[] args) {
		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(5);
		circleSingleLinkedList.showBoy();

		System.out.println("测试小孩出圈");
		/*小孩出圈了: 2
		小孩出圈了: 4
		小孩出圈了: 1
		小孩出圈了: 5
		最后留在圈中的小孩编号: 3*/
		circleSingleLinkedList.countBoy(1, 2, 5);
	}
}

class CircleSingleLinkedList {
	// 创建一个first节点  当前没有编号
	private Boy first = null;

	// 添加小孩节点 构建成一个环形链表
	public void addBoy(int nums) {
		//校验
		if (nums < 1) {
			System.out.println("nums不正确");
			return;
		}
		// 使用for循环创建环形链表
		Boy curBoy = null;
		for (int i = 1; i <= nums; i++) {
			//根据编号 创建小号节点
			Boy boy = new Boy(i);
			// 如果是第一个小孩
			if (i == 1) {
				first = boy;
				first.setNext(first); // 构成环状
				curBoy = first; // 让curBoy 指向第一个小孩
			} else {
				boy.setNext(first);
				curBoy.setNext(boy);
				curBoy = curBoy.getNext();
			}
		}
	}

	//遍历环形链表
	public void showBoy() {
		if (first == null) {
			System.out.println("没有任何小孩");
			return;
		}
		Boy curBoy = first;
		do {
			System.out.println("小孩的编号: " + curBoy.getNo());
			curBoy = curBoy.getNext();
		} while (curBoy != first);
	}

	/**
	 *
	 * @param startNo 从第几个小孩开始数数
	 * @param countNum 表示数几下
	 * @param nums 表示最初有几个小孩
	 */
	public void countBoy(int startNo, int countNum, int nums) {
		if (first == null || startNo < 1 || startNo > nums) {
			System.out.println("输入有误, 请重新输入");
			return;
		}
		Boy helper = first;
		// 1 先将helper指向环形链表的最后
		while (true) {
			if (helper.getNext() == first) {
				break;
			}
			helper = helper.getNext();
		}
		// 小孩报数前 ,先让first 和 helper 移动 k -1 次
		for (int i = 0; i < startNo-1; i++) {
			first = first.getNext();
			helper = helper.getNext();
		}
		//移动出圈  ,这里是个一个循环的操作, 直到圈中只有一个节点
		while (true) {
			if (helper == first) {
				//说明圈中只有一个节点
				break;
			}
			//先让first 和 helper 移动  countNum -1 次
			for (int i = 0; i < countNum - 1; i++) {
				first = first.getNext();
				helper = helper.getNext();
			}
			// 此时first指向的节点, 就是要出圈小孩的节点
			System.out.println("小孩出圈了: " + first.getNo());
			// 这是将first指向的小孩节点出圈
			first = first.getNext();
			helper.setNext(first);
		}
		System.out.println("最后留在圈中的小孩编号: "+ helper.getNo());
	}
}
class Boy {
	private int no; // 编号
	private Boy next; // 指向下一个节点

	public Boy(int no) {
		this.no = no;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public Boy getNext() {
		return next;
	}

	public void setNext(Boy next) {
		this.next = next;
	}
}